#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename T, size_t n, typename cmpare = less<T>>
class MergeSort {
public:
    void dateIn()
    {
        printf("请输入%d个数据:\n");
        for(int i = 0; i < n; ++i)
        {
            T tmp;
            cin >> tmp;
            arr.push_back(tmp);
        }
    }

    void dateOut()
    {
        for(const auto& e: arr)
            cout << e << ' ';
        cout << endl;
    }

    void sort() 
    {
        mergeSort(arr.begin(), arr.end());
    }

private:
    typedef vector<T>::iterator iterator;
    vector<T> arr; 
    T tmp[n];
    cmpare cmp;

    void mergeSort(iterator begin, iterator end)
     {
        if (begin >= end)  break;
        iterator mid = next(begin, distance(v.begin(), v.end()) / 2);
        mergeSort(begin, mid);
        mergeSort(mid + 1, end);
        //合并

        iterator l_start = begin, r_start = mid + 1, l_end = mid + 1;
        int k = 0;
        while(l_start < l_end && r_start < end)
        {
            if(cmp(*l_start, *r_start)) tmp[k++] = *l_start, ++l_start;
            else tmp[k++] = *r_start, ++r_start;
        }
        while( l_start < l_end ) tmp[k++] = *l_start, ++l_start;
        while( r_start < end ) tmp[k++] = *r_start, ++r_start;
        
        k = 0;
        while(begin != end)
        {
            *begin = tmp[k];
            ++begin, ++k;
        }

    }
};

struct student
{
    int _id;
    string _name;
    string _address;
    bool operator> (const student& d)
    {
        return _id > d._id;
    }
    bool operator< (const student& d)
    {
        return _id < d._id;
    }
    void input_info(std::istream& in)
    {
        cout << "输入id号: ";
        in >> _id;
        cout << "name: ";
        in >> _name;
        cout << "输入住址：";
        in >> _address;
    }
};

istream& operator>>(istream& in, student& d)
{
    d.input_info(in);
    return in;
}

int main() {
    // Example usage
    MergeSort<int, 5, greater<int>> sorter;
    sorter.dateIn();
    sorter.sort();
    sorter.dateOut();

    MergeSort<string, 3> string_sort;
    string_sort.dateIn();
    string_sort.sort();
    string_sort.dateOut();


    MergeSort<student, 10, greater<student>> stu_sort;
    stu_sort.dateIn();
    stu_sort.sort();
    stu_sort.dateOut();

    return 0;
}
